// 以下的代码中是使用虚拟头节点的


typedef struct Node {
	int val;
	struct Node* next;
} Node;


typedef struct {
	int size;
	Node* data;
} MyLinkedList;

/** Initialize your data structure here. */

MyLinkedList* myLinkedListCreate() {
	// step 1# 创建一个链表，并创建虚拟头节点
    // 创建一个链表变量:存放头节点和链表长度
    // 分配内存空间
	MyLinkedList* obj = (MyLinkedList*)malloc(sizeof(MyLinkedList));
	// step 1.1# 要手动创建一个虚拟头节点，不能直接让头节点 = NULL 来表示虚拟头节点
    Node* dummyHead = (Node*)malloc(sizeof(Node));
	// 将头节点的 next 指针设置为 NULL，注意 NULL 与 (void *)0 等价
    dummyHead->next = (void*)0;
    // 初始化链表的头节点的长度
	obj->data = dummyHead;
    obj->size = 0;
	return obj;
}

/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int myLinkedListGet(MyLinkedList* obj, int index) {
    // 若索引小于0或大于等于长度，返回-1
    if (index < 0 || index >= obj->size) return -1;

    // 用 cur 指针遍历链表
	Node* cur = obj->data;
	while (index-- >= 0) {
        cur = cur->next;
    }

	return cur->val;
}

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
	// 创建节点
    Node* node = (Node*)malloc(sizeof(Node));
	node->val = val;

    // 新节点的下一个节点先指向头节点后的节点
    // 再把链表的头节点的下一个节点指向新节点
	node->next = obj->data->next;
	obj->data->next = node;
	obj->size++;
}

/** Append a node of value val to the last element of the linked list. */
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {

	// 用 cur 遍历到链表末尾：while循环条件是 cur 的下个节点非空
    Node* cur = obj->data;
	while (cur->next != ((void*)0)) {
        cur = cur->next;
    }
    // 创建新节点并分配空间
	Node* tail = (Node*)malloc(sizeof(Node));
	// 新节点赋值、指向NULL / (void *)0
    tail->val = val;
	tail->next = (void*)0;
    // 将 cur 下一个节点指向新节点，同时 size++
	cur->next = tail;
	obj->size++;
}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
	// 索引非法则return
    if (index > obj->size) return;

    // 用 cur 遍历到第 index 个节点的前一个节点： while循环条件是 index-- > 0
	Node* cur = obj->data;
	while (index-- > 0) { 
        cur = cur->next;
    }

    // 创建新节点
	Node* node = (Node*)malloc(sizeof(Node));
	node->val = val;
    // 先把新节点的下一个节点指向 cur 的下一个节点
    // 再把 cur 的下一个节点指向新节点
    // 同时 size++
	node->next = cur->next;
	cur->next = node;
	obj->size++;
}

/** Delete the index-th node in the linked list, if the index is valid. */
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
	if (index < 0 || index >= obj->size) return;

	Node* cur = obj->data;
	while (index-- > 0) {
        cur = cur->next;
    }

	Node* temp = cur->next;
	cur->next = temp->next;
	free(temp);
	obj->size--;
}

void myLinkedListFree(MyLinkedList* obj) {
    // 用 cur 指向虚拟头节点
	Node* tmp = obj->data;
    // cur 不为空就一直遍历链表
	while (tmp != NULL) {
        // 删除遍历到的节点，并且 cur 后移一位
		Node* n = tmp;
		tmp = tmp->next;
		free(n);
	}
	free(obj);
}

/**
 * Your MyLinkedList struct will be instantiated and called as such:
 * MyLinkedList* obj = myLinkedListCreate();
 * int param_1 = myLinkedListGet(obj, index);
 
 * myLinkedListAddAtHead(obj, val);
 
 * myLinkedListAddAtTail(obj, val);
 
 * myLinkedListAddAtIndex(obj, index, val);
 
 * myLinkedListDeleteAtIndex(obj, index);
 
 * myLinkedListFree(obj);
*/